package a4;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import org.jgrapht.graph.DefaultWeightedEdge;
import org.jgrapht.graph.SimpleWeightedGraph;
import org.jgrapht.graph.WeightedMultigraph;

/**
 * Symmetrisches TSP mit Dreieckungleichung
 */

public class SymTSP {
	//Erwartet immer einen K-Vollständigen Graphen!
	public List<String> SolveTSP(final WeightedMultigraph<String, DefaultWeightedEdge> graph) {
	
		List<DefaultWeightedEdge> list = new ArrayList<>(graph.edgeSet());
		
		Collections.sort(list, new Comparator<DefaultWeightedEdge>() {
			@Override
			public int compare(DefaultWeightedEdge o1, DefaultWeightedEdge o2) {
				return ((Double)graph.getEdgeWeight(o1)).compareTo(graph.getEdgeWeight(o2));
			}			
		}); 
		
		WeightedMultigraph<String, DefaultWeightedEdge> minSkel = new WeightedMultigraph<>(DefaultWeightedEdge.class);
		
		//Minimales Gerüst bestimmen
		   //Greedy Algo
		Map<String, Integer> greedyMap = new HashMap<>();
		int c = 0;
		for(String vertex : graph.vertexSet()) //GreedyMap initialisieren, indem alle Ecken durchnummeriert werden.
			greedyMap.put(vertex, ++c);
		
		for(DefaultWeightedEdge dwe : list){
			String source = graph.getEdgeSource(dwe);
			String target = graph.getEdgeTarget(dwe);
			
			if(!greedyMap.get(source).equals(greedyMap.get(target))) { //Kante darf hinzugefügt werden
				//Nummerierung anpassen
				int min = Math.min(greedyMap.get(source), greedyMap.get(target));
				int max = Math.max(greedyMap.get(source), greedyMap.get(target));
				
				//Alle Elemente, die mit max nummeriert sind, mit min nummerieren
				for(Entry<String,Integer> pair : greedyMap.entrySet())
					if (pair.getValue().equals(max))
						greedyMap.put(pair.getKey(), min);
				
				//Kante ins Gerüst einfügen
				minSkel.addVertex(source);
				minSkel.addVertex(target);				
				minSkel.setEdgeWeight(minSkel.addEdge(source, target), graph.getEdgeWeight(dwe));
			}			
		}
		
		System.out.println(minSkel);
		
		Set<DefaultWeightedEdge> edgeSet = new HashSet<>(minSkel.edgeSet());
		//Kanten verdoppeln
		for(DefaultWeightedEdge edge : edgeSet){
			minSkel.setEdgeWeight(minSkel.addEdge(minSkel.getEdgeSource(edge), minSkel.getEdgeTarget(edge)), minSkel.getEdgeWeight(edge));
		}
		
		//Mit Hierholzer einen Eulerkreis finden
		Hierholzer h = new Hierholzer();
		List<String> tour = h.GetEulerCircle(minSkel);
		//Aus diesem Eulerkreis mehrfach vorkommende Ecken streichen	
		
		List<String> newTour = new ArrayList<String>();
		for(String vertex : tour){
			if(!newTour.contains(vertex)){
				newTour.add(vertex);
			}			
		}
		newTour.add(tour.get(0));
		return newTour;
	}
	
}
